package code1.linkedlist;

/**
 * 原题链接：https://leetcode.cn/problems/design-linked-list/
 */
public class P707 {
    //节点类型
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
    }

    //设计链表
    class MyLinkedList {
        //链表长度
        int length;
        //头结点
        ListNode head;

        public MyLinkedList() {
            length=0;
            head=new ListNode(0);
        }

        //获取下标为index的节点的值: (头结点为第0个节点，链表下标为index的节点则对应第index+1个节点)、(头结点不算进链表的长度和元素)
        public int get(int index) {
            if(index<0 || index>=length){
                return -1;
            }
            ListNode p=head;
            //包含头结点，头结点为第0个节点，下标为index为第index+1个节点
            for(int i=0;i<=index;i++){
                p=p.next;
            }
            return p.val;
        }

        //在头结点后插入
        public void addAtHead(int val) {
            addAtIndex(0, val);
        }

        //在尾节点后插入
        public void addAtTail(int val) {
            addAtIndex(length, val);
        }

        //将一个值为 val 的节点插入到链表中下标为index的节点之前。
        //如果index 等于链表的长度，那么该节点会被追加到链表的末尾。
        //如果index 比长度更大，该节点将不会插入到链表中。
        public void addAtIndex(int index, int val) {
            if(index>length || index<0){
                return;
            }
            length++;
            ListNode p=head;
            //下标为index对应第index+1个节点，故找到第index个节点
            for(int i=0;i<index;i++){
                p=p.next;
            }
            ListNode s=new ListNode(val);
            s.next=p.next;
            p.next=s;
        }

        //删除下标为index的节点
        public void deleteAtIndex(int index) {
            if(index<0 || index>=length){
                return;
            }
            length--;
            ListNode p=head;
            //找到第index个节点
            for(int i=0;i<index;i++){
                p=p.next;
            }
            p.next=p.next.next;
        }
    }
}
